﻿// 0806train01.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <unordered_map>
#include <algorithm>
#include <limits.h>

using namespace std;


/*
 给定一个矩阵，包含N*M个整数，和一个包含K个整数的数组，
 现在要求在这个矩阵中找一个宽度最小的子矩阵，要求子矩阵包含数组中所有的整数。

输入描述
第一行输入两个正整数N，M，表示矩阵大小。
接下来N行M列表示矩阵内容。下一行包含一个正整数K。下一行包含K个整数，表示所需包含的数组，K个整数可能存在重复数字。
所有输入数据小于1000。

输出描述
输出包含一个整数，表示满足要求子矩阵的最小宽度，若找不到，输出-1

输入
2 5
1 2 2 3 1
2 3 2 3 2
3
1 2 3
输出
2
 */

unordered_map<int,int>GetTargetMap(const vector<int>& target_vec)
{
    unordered_map<int, int>target_map;
    
    for (auto&num: target_vec)
    {
        target_map[num] += 1;
    }

    return target_map;
    //GetTargetMap------
}

vector<unordered_map<int,int>>GetMapVec(vector<vector<int>>& oh_vec)
{
    int height_size = oh_vec.size();
    int width_size = oh_vec[0].size();

    vector<unordered_map<int, int>>result_vec(width_size);
    for (int w_1=0; w_1<width_size; w_1++)
    {
        unordered_map<int, int>col_map;
        for (int h_2=0; h_2<height_size; h_2++)
        {
            int curr_num = oh_vec[h_2][w_1];
            col_map[curr_num] += 1;

        }
        result_vec[w_1] = col_map;
    }
    return result_vec;
    //GetVecMap
}

bool IsContain(int left_index,int right_index, 
    const vector<unordered_map<int, int>>map_vec,
    const unordered_map<int, int>target_map
)
{
    unordered_map<int, int>curr_map;

    for (int i=left_index; i<=right_index;i++)
    {
        unordered_map<int, int>mini_map = map_vec[i];
        for (auto map_item:mini_map)
        {
            curr_map[map_item.first] += map_item.second;
        }
    }

    bool result = true;

    for (auto&t_item: target_map)
    {
        if (curr_map[t_item.first]<t_item.second)
        {
            result = false;
        }
    }

    return result;
    //IsContain
}


void solve01(vector<vector<int>>&oh_vec, vector<int>&target_vec)
{
    //1left_index=0,right_index=0,扩大右窗
    //2拿到vector<unordered_map<int,int>>curr_map_vec
    //3比较curr_map_vec和target_map，如果curr_map_vec[item.first]<target_map[item.first] false
    //4如果比较结果为true，收缩左窗

    unordered_map<int, int>target_map = GetTargetMap(target_vec);

    vector<unordered_map<int, int>>map_vec = GetMapVec(oh_vec);

    //for (auto&oh_map:map_vec)
    //{
	   // for (auto&map_item:oh_map)
	   // {
    //        cout << map_item.first << ' ';
	   // }
    //    cout << '\n';
    //}
    int result = INT_MAX;
    int left_index = 0;
    
    int vec_width = map_vec.size();
    for (int right_index=0; right_index<vec_width; right_index++)
    {
        while (IsContain(left_index,right_index,map_vec,target_map))
        {
            result = min(result, right_index - left_index + 1);

            left_index += 1;
        }

    }

    if (result==INT_MAX)
    {
        cout << -1;
        return;
    }

    cout << result;
    //------
}



bool CheckVerify(unordered_map<int, int>& window_map, 
    const unordered_map<int, int>target_map
    )
{
    bool result = true;

    for (auto& t_item : target_map)
    {
        if (window_map[t_item.first] < t_item.second)
        {
            result = false;
        }
    }

    return result;
}

void solve11(vector<vector<int>>& oh_vec, vector<int>& target_vec)
{
    //1left_index=0,right_index=0,扩大右窗
    //2拿到vector<unordered_map<int,int>>curr_map_vec
    //3比较curr_map_vec和target_map，如果curr_map_vec[item.first]<target_map[item.first] false
    //4如果比较结果为true，收缩左窗

    unordered_map<int, int>target_map = GetTargetMap(target_vec);

    vector<unordered_map<int, int>>map_vec = GetMapVec(oh_vec);

    int result = INT_MAX;
    int left_index = 0;

    unordered_map<int, int>curr_map;
    
	unordered_map<int, int>window_map = map_vec[0];
	for (auto map_item : window_map)
	{
		curr_map[map_item.first] += map_item.second;
	}

    //左窗（即将丢弃）
    int prev_index = left_index;
    int vec_width = map_vec.size();
    for (int right_index = 1; right_index < vec_width; right_index++)
    {
        //右窗扩大
        int new_index = right_index;
        unordered_map<int, int>new_map = map_vec[new_index];
        for (auto& map_item : new_map)
        {
            window_map[map_item.first] += map_item.second;
        }

        while (CheckVerify(window_map,target_map)&&left_index<=right_index)
        {
            result = min(result, right_index - left_index + 1);

            //收缩左窗
            unordered_map<int, int>prev_map = map_vec[prev_index];
            for (auto& map_item : prev_map)
            {
                window_map[map_item.first] -= map_item.second;
            }
            left_index += 1;
            prev_index = left_index;
        }

    }

    if (result == INT_MAX)
    {
        cout << -1;
        return;
    }

    cout << result;
    //------
}


/*
 假如车辆的颜色只有 3 种，找出 N 秒内经过的最多颜色的车辆数量，三种颜色编号为 0, 1, 2。
输入
第一行输入的是通过的车辆颜色信息。比如[0, 1, 1, 2] 代表 4 秒钟通过的车辆颜色分别是 0, 1, 1, 2
第二行输入的是统计时间窗，整型，单位为秒。
输出
输出指定时间窗内经过的最多颜色的车辆数量

示例1
0 1 2 1
3
输出
2
说明
在[1,2,1]这个 3 秒时间窗内，1 这个颜色出现 2 次，数量最多
 */


void solve02(vector<int>&oh_vec, int limit)
{
    vector<int>window_vec = { 0,0,0 };

    if (limit>oh_vec.size())
    {
        for (int i = 0; i < oh_vec.size(); i++)
        {
            int curr_num = oh_vec[i];
            window_vec[curr_num] += 1;
        }

        int result = max(window_vec[0], max(window_vec[1], window_vec[2]));

        cout << result;
        return;
    }

    for (int i=0; i<=limit-1;i++)
    {
        int curr_num = oh_vec[i];
        window_vec[curr_num] += 1;
    }

    int result = max(window_vec[0], max(window_vec[1], window_vec[2]));

    int vec_size = oh_vec.size();
    int prev_index = 0;
    int curr_max_count = result;
    for (int left_index=1,right_index=limit; right_index<vec_size; left_index++,right_index++)
    {
        int prev_num = oh_vec[prev_index];
        window_vec[prev_num] -= 1;

        int new_num = oh_vec[right_index];
        window_vec[new_num] += 1;

        curr_max_count = max(window_vec[0], max(window_vec[1], window_vec[2]));

        result = max(result, curr_max_count);
        prev_index = left_index;
        //for------
    }
    cout << result;
    //solve02------
}


/*
 新词挖掘：给出一个待挖掘文本内容字符串content和一个词的字符串word，找到content中所有word的新词。
新词：使用词word的字符排列形成的字符串。
请帮小华实现新词挖掘，返回发现的新词的数量。
输入描述
第一行输入为待挖掘的文本内容content；
第二行输入为词word；
输出描述
在中找到的所有word的新词的数量。

示例1
输入
qweebaewqd
qwe
输出
2

说明
起始索引等于 0 的子串是 qwe, 它是 word的新词。
起始索引等于 6 的子串是 ewq, 它是 word的新词。
 */

bool IsTarget03(unordered_map<char, int>&window_map, unordered_map<char, int>target_map)
{
    bool result = true;

    for (auto&map_item:target_map)
    {
        char key = map_item.first;
        if (window_map[key]!=map_item.second)
        {
            result = false;
            break;
        }
    }
    return result;
}

void solve03(string &oh_str, string &target_str)
{
    //1unordered_map<char,int>target_map
    //2unordered_map<char,int>window_map
    //3比较target_map和window_map
    //4更新prev_index

    unordered_map<char, int>target_map;
    for (auto&oh_char:target_str)
    {
        target_map[oh_char] += 1;
    }
    int limit = target_str.size();

    string origin_str = oh_str.substr(0, limit);

    unordered_map<char, int>window_map;
    for (auto&oh_char:origin_str)
    {
        window_map[oh_char] += 1;
    }
    int result = 0;
    if (IsTarget03(window_map, target_map))
        result += 1;

    int vec_size = oh_str.size();
    int prev_index = 0;
    for (int left_index=1,right_index=limit; right_index<vec_size; left_index++,right_index++)
    {
        char prev_char = oh_str[prev_index];
        window_map[prev_char] -= 1;

        char new_char = oh_str[right_index];
        window_map[new_char] += 1;

        if (IsTarget03(window_map, target_map))
        {
            result += 1;
        }
        //重要，更新prev_index
        prev_index = left_index;
    }

    cout << result;
    //solve03
}

int main()
{
	{
        //qweebaewqd
        //qwe
        //string oh_str = "qweebaewqd";
        //string target_str = "qwe";
        string oh_str;
        cin >> oh_str;
        string target_str;
        cin >> target_str;

        solve03(oh_str, target_str);

        return 0;
	}


	{
        //vector<int>oh_vec = { 0,1,2,1 };
        //int limit = 3;
        //0 1 2 1
		//3
        string input;
        getline(cin, input);
        stringstream oh_sstream(input);
        vector<int>oh_vec;
        string token;
        while (oh_sstream>>token)
        {
            oh_vec.push_back(stoi(token));
        }

        //for (auto&num:oh_vec)
        //{
        //    cout << num << ' ';
        //}

        int limit;
        cin >> limit;

        solve02(oh_vec, limit);

        return 0;
	}

    //1 2 2 3 1
	//2 3 2 3 2
    vector<int>vec_1 = { 1,2,2,3,1 };
    vector<int>vec_2 = { 2,3,2,3,2 };
    vector<int>target_vec = { 1,2,3 };

    vector<vector<int>> oh_vec = { vec_1, vec_2 };

    //2height 5width
	//1 2 2 3 1
	//2 3 2 3 2
	//3
	//1 2 3

    //int height, width;
    //cin >> height >> width;
    //vector<vector<int>>oh_vec(height, vector<int>(width));
    //for (int h_1=0; h_1<height;h_1++)
    //{
    //    for (int w_2=0; w_2<width;w_2++)
    //    {
    //        cin>>oh_vec[h_1][w_2];
    //    }
    //}

    //for (auto&mini_vec:oh_vec)
    //{
	   // for (auto&num:mini_vec)
	   // {
    //        cout << num << ' ';
	   // }
    //    cout << '\n';
    //}

    //int target_size;
    //cin >> target_size;
    //vector<int>target_vec(target_size);
    //for (int i=0; i<target_size;i++)
    //{
    //    cin >> target_vec[i];
    //}

    //for (auto&num:target_vec)
    //{
    //    cout << num << ' ';
    //}

    solve11(oh_vec, target_vec);
}

// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单

// 入门使用技巧: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件
